\section{Conclusion}
In this paper we prove a tight unconditional lower bound on the time complexity of distributed random walk computation, implying that the algorithm in \cite{DasSarmaNPT-PODC10} is time optimal. To the best of our knowledge, this is the first lower bound that the diameter plays a role of multiplicative factor. Our proof technique comes from strengthening the connection between communication complexity and distributed algorithm lower bounds initially studied in \cite{DasSarmaHKKNPPW10} by associating {\em rounds} in communication complexity to the distributed algorithm running time, with network diameter as a trade-off factor.
%Our technique can be of independent interest and may be useful in showing non-trivial lower bounds on the complexity of other fundamental distributed computing problems.

In light of the success in proving distributed algorithm lower bounds from communication complexity in this and the previous work~\cite{DasSarmaHKKNPPW10}, it is interesting to explore further applications of this technique. One interesting approach is to show a connection between distributed algorithm lower bounds and other models of communication complexity, such as multiparty and asymmetric communication complexity (see, e.g., \cite{KNbook}).
%
Potential applications of this technique are distance-related problems such as shortest $s$-$t$ path, single-source distance computation, and spanner construction. The lower bound of $\Omega(\sqrt{n})$ are shown in \cite{DasSarmaHKKNPPW10} for these types of problems and stronger lower bounds such as $\Omega(\sqrt{n D})$ or $\Omega(n)$ are still possible. 
%
Another problem left open is showing a lower bound of performing a long walk. For example, one can generate a {\em random spanning tree} by computing a walk of length equals the cover time (using the version where every node knows their positions). It is interesting to see if performing such a walk can be done faster. Additionally, the upper and lower bounds of the problem of generating a random spanning tree itself is very interesting since its current upper bound of $\tilde O(\sqrt{m}D)$~\cite{DasSarmaNPT-PODC10} simply follows as an application of random walk computation~\cite{DasSarmaNPT-PODC10} while no lower bound is known.


